public class Solution6 {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null)
            return null;
        ListNode list1 = new ListNode();
        ListNode list1Tail = list1;
        ListNode list2 = new ListNode();
        ListNode list2Tail = list2;

        ListNode cur = pHead;
        while(cur!=null){
            if(cur.val<x){
                list1Tail.next=cur;
                cur=cur.next;
                list1Tail=list1Tail.next;
            }
            else{
                list2Tail.next = cur;
                cur = cur.next;
                list2Tail=list2Tail.next;
            }
        }
        list1Tail.next = list2.next;
        list2Tail.next=null;
        return list1.next;
    }
}